package algorithm.middle;

import org.omg.CORBA.MARSHAL;
import pojo.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
 * <p>
 * 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
 * 矩阵的列数 n 应该等于 2height+1 - 1 。
 * 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
 * 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
 * 继续这一过程，直到树中的所有节点都妥善放置。
 * 任意空单元格都应该包含空字符串 "" 。
 * 返回构造得到的矩阵 res 。
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/print-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PrintTree655 {

    String[][] arr;
    int high;

    public List<List<String>> printTree(TreeNode root) {
        //1.统计层数
        high = fun(root, 0);
        //2.计算座位
        arr = new String[high][(int) (Math.pow(2, high) - 1)];
        for (String[] strings : arr) {
            Arrays.fill(strings, "");
        }
        //每一层所在的点为，上个点的下层左或右
        //左右间隔距离为 2^( high - row - 1)
        DFS(0, arr[0].length / 2, root);
        List<List<String>> res = new ArrayList<>();
        for (String[] strings : arr) {
            res.add(Arrays.asList(strings));
        }
        return res;
    }

    public int fun(TreeNode root, int i) {
        if (root == null) return i;
        i++;
        return Math.max(fun(root.left, i), fun(root.right, i));
    }

    public void DFS(int row, int col, TreeNode node) {
        arr[row][col] = node.val + "";
        row++;
        if (node.left != null) {
            DFS(row, col - (int) Math.pow(2, high - row - 1), node.left);
        }
        if (node.right != null) {
            DFS(row, col + (int) Math.pow(2, high - row - 1), node.right);
        }
    }
}
